package fun.coding.leetcode;

import java.util.HashSet;
import java.util.Set;

public class IntersectionOfTwoLinkedLists {

	public static void main(String[] args) {

	}

	// Good thinking about the difference
	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		return null;
	}
	
	// This is extra space, not what they want
	// TODO: use two pointers, p1 is length difference ahead
	public ListNode getIntersectionNodeONSpace	(ListNode headA, ListNode headB) {
		Set<ListNode> s = new HashSet<ListNode>();
		
		while (headA != null) {
			s.add(headA);
			headA = headA.next;
		}
		
		while (headB != null) {
			if (s.contains(headB)) {
				return headB;
			}
			headB = headB.next;
		}
		
		return null;
	}
}
